package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Objects;

public class Main {

	public static void main(String[] args) {
		
		System.out.println(count(new int[] {1,2,3,3,3,3,4,5},3));
	}

	public static int count(int[] arr, int target) {

		// 1.参数校验 //
		Objects.requireNonNull(arr, "参数arr不能为null");

		// 2.求出firstIndex、lastIndex，计算target出现的次数 //
		int firstIndex = firstIndex(arr, target);
		if (firstIndex < 0) { // target不存在于arr中
			return 0;
		}
		int lastIndex = lastIndex(arr, target);
		return lastIndex - firstIndex + 1;
	}

	private static int firstIndex(int[] arr, int target) {

		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] < target) {
				low = mid + 1;
			} else if (arr[mid] > target) {
				high = mid - 1;
			} else {
				if (mid > 0 && arr[mid - 1] == target) {
					high = mid - 1;
				} else {
					return mid;
				}
			}
		}
		return -1;
	}

	private static int lastIndex(int[] arr, int target) {

		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] < target) {
				low = mid + 1;
			} else if (arr[mid] > target) {
				high = mid - 1;
			} else {
				if (mid < arr.length-1 && arr[mid + 1] == target) {
					low = mid + 1;
				} else {
					return mid;
				}
			}
		}
		return -1;
	}
}
